#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
using namespace std;

bool isPanlidrome(int x)
{
	if(x<0)
		return false;
	if(x/10 == 0)
		return true;
	int ibit = 10;
	while(x/ibit >= 10)
	{
		ibit *= 10;
	}
	while(x!=0)
	{
		int l = x/ibit;
		int r = x%10;
		if(l!=r)
			return false;
		//shrink x
		x = (x%ibit) / 10;
		ibit /= 100;
	}
	return true;
}

//longest panlindrome string
//using dp O(n^2)

string expendString(string s, int l, int r)
{
	//string ret="";
	int n = s.length();
	while(l>=0 && r<n &&s[l]==s[r])
	{
		l--;
		r++;
	}
	return s.substr(l+1,r-l-1);
}

string maxPanlidrome(string s)
{
	int n = s.length();
	if(n<=1)
		return s;
	string ret = s.substr(0,1);
	for(int i=0;i<n;++i)
	{
		string p1 = expendString(s,i,i);
		if(p1.length() > ret.length() )
			ret = p1;
		string p2 = expendString(s,i,i+1);
		if(p2.length() > ret.length() )
			ret = p2;
	}
	return ret;
}

//mache's algorithm 
//O(n)
int min(int a, int b)
{
	return (a>=b) ? b : a;
}

string ProcessString(string s)
{
	int n = s.length();
	if(n==0)
		return "";
	string ret="^";
	for(int i=0; i<n;++i)
		ret += "#"+s.substr(i,1);
	ret +="#$";
	return ret;
}

string maxnPanlidrome(string s)
{
	int n = s.length();
	if(n<=1)
		return s;
	string T = ProcessString(s);
	int n_size = T.length();
	int *p = new int[n_size];
	memset(p,0,n*sizeof(int));
	int C=0,R=0;
	for(int i=1;i<n-1;++i)
	{
		int mirror_i = 2*C - R;
		p[i] = (R>i) ? min(R-i,p[mirror_i]) : 0;

		while(T[i+1+p[i]] == T[i-1-p[i]])
			p[i]++;
		if(i+p[i]>R)
		{
			C = i;
			R = i+p[i];
		}
	}

	int centerindex = 0, maxLength=0;
	for(int i=0; i< n; ++i)
	{
		if(p[i]>maxLength)
		{
			centerindex = i;
			maxLength = p[i];
		}
	}

	return s.substr((centerindex-1-maxLength)/2, maxLength);

}



int main()
{
	cout<<isPanlidrome(101)<<endl;
	return 0;
}